1. Field of the Invention
This invention relates to apparatus for generating graphical images, and is particularly concerned with the process of converting information describing a scene to be represented into a rasterised image.
2. Description of Related Art
Spatial partitioning is a technique which allows a problem to be broken down into a number of smaller more soluble problems. In the field of computer graphics, objects to be represented in an environment are defined in terms of three-dimensional data, which then needs to be rendered into rasterised two-dimensional data to be displayed on a VDU. From a particular viewpoint, the projections of the objects may overlap significantly, which can lead to very difficult computations having to be made.
By breaking down the larger rendering problem into a number of smaller problems, the overall rendering process can be made easier. As described in xe2x80x9cComputer Graphics Principles and Practicesxe2x80x9d by Foley, Van Dam, Feiner and Hughes, 2nd Edition, Addison-Wesley Publishing Company, ISBN 0-201-12110-7) pp 664-680, it is possible to partition a space by superimposing a three-dimensional grid over a space within which objects are defined, and then each grid box can be processed independently.
Adaptive partitioning, in which the size of partitions within the space varies, involves the sub-division of the space to be rendered according to a recursive process, until a termination criterion is reached. For example, sub-division may stop when there are fewer than a maximum number of objects in a partition.
The partitioning information can be carried in a data structure such as a binary space partition tree (BSP). However, a BSP tree can become unwieldy if partitioning is carried out incorrectly. A number of nodes of the BSP tree may become difficult to process or time consuming in that they represent nearly empty partitions of the space. Moreover, arbitrary partitioning of a space may lead to division of objects between two parts of a space. This can actually increase the computational expense of the rendering process.
It is object of at least an aspect of the invention to provide an improved means of partitioning a space preliminary to rendering procedures.
According to a first aspect of the invention, apparatus for arranging data defining a scene to be represented graphically comprises means for partitioning the scene by means of a plane oriented in a selected one of a predetermined set of directions, the means for partitioning being operable to select the direction and position of the plane with reference to the content of the scene.
According to a second aspect of the invention, a method for arranging data defining a scene to be represented graphically comprises the steps of defining a predetermined set of partition directions, processing the content of the scene to identify a suitable partition plane in one of those predetermined directions, and partitioning the scene by means of the partition plane.